package likou.offer;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/30 07:54
 */
public class _37_2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(4);
        String serialize = serialize(root);
        System.out.println(serialize);
        root = deserialize(serialize);
        System.out.println(root);
    }

    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder(1024);
        recursive(sb, root);
        return sb.toString();
    }

    private static void recursive(StringBuilder sb, TreeNode node) {
        sb.append((char) (node.val + '0'));
        if (node.left == null) {
            sb.append('#');
        } else {
            recursive(sb, node.left);
        }
        if (node.right == null) {
            sb.append('#');
        } else {
            recursive(sb, node.right);
        }
    }

    static String data;
    static int index = 0;

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        return deRecursive(data);
    }

    private static TreeNode deRecursive(String data) {
        if (data.charAt(index) == '#') {
            ++index;
            return null;
        }
        TreeNode node = new TreeNode(data.charAt(index++) - '0');
        node.left = deRecursive(data);
        node.right = deRecursive(data);
        return node;
    }
}
